package com.zwy.alhorthms;

import jdk.nashorn.internal.ir.ReturnNode;

/**
 * 快速排序 使用中轴，划分大小
 * 解决最坏的情况，数组已经排序好，或者已经逆序排序好，
 * 第一种：进行判读，如果数组已经是持续增长型，则不进行快速排序
 * 第二种，随机选取中轴基准，将其替换为每个区的最后一位
 *
 * @author 天火
 * @className QuickSort
 */
public class QuickSort {


    public static void main(String[] args) {
        int[] arr = {7, 3, 2, 6,8,1, 9, 5,4,10};
        sort(arr,0,arr.length -1);
        print(arr);

    }

    public static void sort(int[] arr,int leftBound,int rightBound) {


        if(leftBound >= rightBound){
            return;
        }
        int pivot = arr[rightBound];
        int left = leftBound;
        int right = rightBound -1;
        //如果当前的左指针 大于于中轴基准，和当前右指针指向的值小于中轴基准，则进行交换
        while (left <= right) {
            while (left <= right && arr[left] <= pivot) {
                left++;
            }

            while (left <= right && arr[right] > pivot) {
                right--;
            }
            if(left < right){
                swap(arr, left, right);
                System.out.print("第一个开始交换: ");
                print(arr);
            }
        }

        //一次循环结束后
        swap(arr, left, rightBound);

        System.out.print("交换基准: ");
        print(arr);
        //小区排序
        sort(arr,leftBound,left-1);
        //大区排序
        sort(arr,left+1,rightBound);
    }

    static void swap(int[] arr, int j, int i) {
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

    static void print(int[] arr) {
        for (int value : arr) {
            System.out.print(value + "    ");
        }
        System.out.println();
    }
}
